package leetcode_301_400;

import com.sun.corba.se.spi.ior.iiop.IIOPFactories;

import java.lang.reflect.Constructor;
import java.util.HashSet;
import java.util.Set;

public class LeeCode_309_timeout {
    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{1, 2, 3, 0, 2}));
        System.out.println(maxProfit(new int[]{1}));
    }
    private static int maxProfit(int[] prices) {
        int n = prices.length;
        int max = Integer.MIN_VALUE;
        int[] maxes = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            if (prices[i] > max){
                max = prices[i];
            }
            maxes[i] = max;
        }
        int[] ans = new int[1];
        Set<String> set = new HashSet<>();
        dfs(prices, maxes, 0, 0, ans, -1, set);
        return ans[0];
    }
    private static void dfs(int[] prices, int[] maxes, int s, int sum, int[] ans, int have, Set<String> set){
        String key = s + "," + sum + "," + have;
        if (set.contains(key))
            return;
        set.add(key);
        if (s >= prices.length){
            ans[0] = Math.max(ans[0], sum);
            return;
        }
        if (maxes[s] < have){
            return;
        }
        if (have < 0){
            if (prices[s] < maxes[s]){
                dfs(prices, maxes, s + 1, sum, ans, prices[s], set);
            }
        }else {
            if (prices[s] > have){
                dfs(prices, maxes, s + 2, sum + (prices[s] - have), ans, -1, set);
            }
        }
        dfs(prices, maxes, s + 1, sum, ans, have, set);
    }
}
